package problem1054;

import java.util.HashMap;

//1054.距离相等的条形码
//https://leetcode.cn/problems/distant-barcodes/description/

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int maxCount = 0;
        int k = 0;
        for(int x:barcodes) {
            map.put(x, map.getOrDefault(x,0)+1);
            if(map.get(x) > maxCount) {
                maxCount = map.get(x);
                k = x;
            }
        }
        int n = barcodes.length;
        int index = 0;
        for(int i = 0; i<maxCount; i++) {
            barcodes[index] = k;
            index += 2;
        }
        map.remove(k);
        for(int x : map.keySet()) {
            for(int i = 0; i<map.get(x); i++) {
                if(index >= n) index = 1;
                barcodes[index] = x;
                index += 2;
            }
        }
        return barcodes;
    }
}